// This is the file to include in your code if you want access to the
// complete LList template class

// First, get the declaration for the base list class
#ifndef LIST
#include "list.h"
#endif
#include "Link.h"

// Linked list implementation
template <class Elem> 
class LList: public List<Elem> {
private:
  Link<Elem>* head;       // Pointer to list header
  Link<Elem>* tail;       // Pointer to last Elem in list 
  Link<Elem>* fence;      // Last element on left side
  i32 leftcnt;            // Size of left partition
  i32 rightcnt;           // Size of right partition
  void init() {           // Intialization routine
    fence = tail = head = new Link<Elem>;
    leftcnt = rightcnt = 0;
  }
  void removeall() {   // Return link nodes to free store
    _while(head != NULL)
      {
	fence = head;
	head = head->next;
	delete fence;
      }_end_while;
  }
public:
  LList(i32 size=DefaultListSize) { init(); }
  ~LList() { removeall(); }  // Destructor
  void clear() { removeall(); init(); }
  boolean insert(const Elem&);
  boolean append(const Elem&);
  boolean remove(Elem&);
  void setStart()
    { fence = head; rightcnt += leftcnt; leftcnt = 0; }
  void setEnd()
    { fence = tail; leftcnt += rightcnt; rightcnt = 0; }
  void prev();
  void next() {
    _if(fence != tail) // Don't move fence if right empty
      {
	fence = fence->next; rightcnt--; leftcnt++;
      }_end_if;
  }
  i32 leftLength() const  { return leftcnt; }
  i32 rightLength() const { return rightcnt; }
  boolean setPos(i32 pos);
  boolean getValue(Elem& it) const {
    _if(rightLength() == 0)
      {
	return false;
      }_end_if;
    it = fence->next->element;
    return true;
  }
  void print() const;
};

template <class Elem> // Insert at front of right partition
boolean LList<Elem>::insert(const Elem& item) {
  fence->next = new Link<Elem>(item, fence->next);  
  _if(tail == fence)
    {
      tail = fence->next;  // New tail
    }_end_if;
  rightcnt++;
  return true;
}

template <class Elem> // Append Elem to end of the list
boolean LList<Elem>::append(const Elem& item) {
  tail = tail->next = new Link<Elem>(item, NULL);
  rightcnt++;
  return true;
}

// Remove and return first Elem in right partition
template <class Elem> bool LList<Elem>::remove(Elem& it) {
  _if(fence->next == NULL)
    {
      return false; // Empty right
    }_end_if;
  it = fence->next->element;       // Remember value
  Link<Elem>* ltemp = fence->next; // Remember link node
  fence->next = ltemp->next;       // Remove from list
  _if(tail == ltemp)
    {
      tail = fence; // Reset tail
    }_end_if;
  delete ltemp;                    // Reclaim space
  rightcnt--;
  return true;
}

// Move fence one step left; no change if left is empty
template <class Elem> void LList<Elem>::prev() {
  Link<Elem>* temp = head;
  _if(fence == head)
    {
      return; // No previous Elem
    }_end_if;
  _while(temp->next!=fence) 
    {
      temp=temp->next;
    }_end_while;
  fence = temp;
  leftcnt--; rightcnt++;
}

// Set the size of left partition to pos
template <class Elem> boolean LList<Elem>::setPos(i32 pos) {
  _if((pos < 0) || (pos > rightcnt+leftcnt))
    {
      return false;
    }_end_if;
  fence = head;
  _for(i32 i=0, i<pos, i++)
    {
      fence = fence->next;
    }_end_for;
  return true;
}

template <class Elem> void LList<Elem>::print() const {
  Link<Elem>* temp = head;
  std::cout << "< ";
  _while (temp != fence) {
    std::cout << temp->next->element << " ";
    temp = temp->next;
  }_end_while;
  std::cout << "| ";
  _while (temp->next != NULL) {
    std::cout << temp->next->element << " ";
    temp = temp->next;
  }_end_while;
  std::cout << ">\n";
}
